package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.CheckUtils;
import util.PrinterUtils;

import java.util.ArrayList;
import java.util.List;


/**
 * 4-opt
 * https://github.com/Valdecy/pyCombinatorial/blob/main/pyCombinatorial/algorithm/opt_4.py
 */
public class Ls4opt extends LocalSearch {


    public Ls4opt(Problem problem) {
        super(problem);
    }

    @Override
    public void solve() {
        Solution initSolution = initial();
        PrinterUtils.printTspResult("local search 4opt init", initSolution);
        Solution finalSolution = improve(initSolution);
        PrinterUtils.printTspResult("local search 4opt final", finalSolution);
        CheckUtils.check(finalSolution, distance);
    }


    @Override
    protected Solution improve(Solution solution) {
        int n = solution.length();
        Solution currentSolution = solution.copy();

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        List<Integer> currPath = new ArrayList<>(currentSolution.getPermutation());
                        int currCost = currentSolution.getCost();
                        List<List<Integer>> newPermutations = makeMove(currentSolution.getPermutation(), i, j, k, l);
                        for (List<Integer> path : newPermutations) {
                            int cost = calculateFitness(path);
                            if (cost < currCost) {
                                currPath = path;
                                currCost = cost;
                            }
                        }
                        if (currCost < currentSolution.getCost()) {
                            currentSolution = new Solution(currPath, currCost);
                        }
                    }
                }
            }
        }

        return currentSolution;
    }


    private List<List<Integer>> makeMove(List<Integer> permutation, int i, int j, int k, int l) {
        List<Integer> A = new ArrayList<>(permutation.subList(0, j + 1));
        List<Integer> B = new ArrayList<>(permutation.subList(j + 1, k + 1));
        List<Integer> C = new ArrayList<>(permutation.subList(k + 1, l + 1));
        List<Integer> D = new ArrayList<>(permutation.subList(l + 1, permutation.size()));
        List<Integer> a = new ArrayList<>(permutation.subList(0, i + 1));
        a.addAll(reverse(permutation.subList(i + 1, j + 1)));
        List<Integer> b = reverse(B);
        List<Integer> c = reverse(C);
        List<Integer> d = reverse(D);

        // 47 kind of variants
        List<List<Integer>> res = new ArrayList<>();
        res.add(merge(A, C, B, D));
        res.add(merge(A, C, D, B));
        // 1
        res.add(merge(a, B, C, D));
        res.add(merge(a, C, B, D));
        res.add(merge(a, C, D, B));

        res.add(merge(A, b, C, D));
        res.add(merge(A, C, b, D));
        res.add(merge(A, C, D, b));

        res.add(merge(A, B, c, D));
        res.add(merge(A, c, B, D));
        res.add(merge(A, c, D, B));

        res.add(merge(A, B, C, d));
        res.add(merge(A, C, B, d));
        res.add(merge(A, C, d, B));

        // 2
        res.add(merge(a, b, C, D));
        res.add(merge(a, C, b, D));
        res.add(merge(a, C, D, b));

        res.add(merge(a, B, c, D));
        res.add(merge(a, c, B, D));
        res.add(merge(a, c, D, B));

        res.add(merge(a, B, C, d));
        res.add(merge(a, C, B, d));
        res.add(merge(a, C, d, B));

        res.add(merge(A, b, c, D));
        res.add(merge(A, c, b, D));
        res.add(merge(A, c, D, b));

        res.add(merge(A, b, C, d));
        res.add(merge(A, C, b, d));
        res.add(merge(A, C, d, b));

        res.add(merge(A, B, c, d));
        res.add(merge(A, c, B, d));
        res.add(merge(A, c, d, B));

        // 3
        res.add(merge(a, b, c, D));
        res.add(merge(a, c, b, D));
        res.add(merge(a, c, D, b));

        res.add(merge(a, b, C, d));
        res.add(merge(a, C, b, d));
        res.add(merge(a, C, d, b));

        res.add(merge(a, B, c, d));
        res.add(merge(a, c, B, d));
        res.add(merge(a, c, d, B));

        res.add(merge(A, b, c, d));
        res.add(merge(A, c, b, d));
        res.add(merge(A, c, d, b));

        // 4
        res.add(merge(a, b, c, d));
        res.add(merge(a, c, b, d));
        res.add(merge(a, c, d, b));

        return res;
    }

    private List<Integer> merge(List<Integer> a, List<Integer> b, List<Integer> c, List<Integer> d) {
        List<Integer> s = new ArrayList<>();
        s.addAll(a);
        s.addAll(b);
        s.addAll(c);
        s.addAll(d);
        return s;
    }

    private List<Integer> reverse(List<Integer> s) {
        List<Integer> r = new ArrayList<>();
        for (int i = 0; i < s.size(); i++) {
            r.add(s.get(s.size() - 1 - i));
        }
        return r;
    }

}
